1. Field of the Invention
This invention relates generally to computer program execution systems, e.g., optimizing compilers, and more specifically, to a sampling-based system and method implementing yield points in executing programs to enable the checking of multiple system conditions, and invocation of different runtime services when the yield point is taken in order to adaptively optimize software application during runtime.
2. Discussion of the Prior Art
The dynamic nature of the Java programming language presents both the largest challenge and the greatest opportunity for high-performance Java implementations. Language features such as dynamic class loading and reflection prevent straightforward applications of traditional static compilation and interprocedural optimization. As a result, Java Virtual Machine (JVM) implementors have invested significant effort in developing dynamic compilers for Java. Because dynamic compilation occurs during application execution, dynamic compilers must carefully balance optimization effectiveness with compilation overhead to maximize total system performance. However, dynamic compilers may also exploit runtime information to perform optimizations beyond the scope of a purely static compilation model.
The first wave of virtual machines provided Just-In-Time (JIT) compilation that relied on simple static strategies to choose compilation targets, typically compiling each method with a fixed set of optimizations the first time it was invoked. These virtual machines include early work such as the Smalltalk-80 as described in “Efficient implementation of the Smalltalk-80 System”, 11th Annual ACM Symposium on the Principles of Programming Languages, pages 297–302, January 1984, and Self-91 such as described in the references “Making pure object-oriented languages practical”, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1–15, November 1991 to C. Chambers et al. and “The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages”, Craig Chambers PhD thesis, Stanford University, March 1992 published as technical report STAN-CS-92-1420, as well as a number of more recent Java systems such as described in A.-R. Adl-Tabatabai, et al., “Fast, effective code generation in a Just-in-Time Java compiler,” Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation (PLDI), pages 280–290, Montreal, Canada, 17–19 Jun. 1998 and SIGPLAN Notices, 33(5), May 1998, M. G. Burke, et al., “The Jalapeno dynamic optimizing compiler for Java”, ACM 1999 Java Grande Conference, pages 129–141, June 1999, A. Krall et al., “Efficient Java VM Just-in-Time compilation”, J.-L. Gaudiot, editor, International Conference on Parallel Architectures and Compilation Techniques, pages 205–212, October 1998, and, B.-S. Yang, et al., “LaTTe: A Java VM Just-in-Time compiler with fast and efficient register allocation”, International Conference on Parallel Architectures and Compilation Techniques, October 1999.
A second wave of more sophisticated virtual machines moved beyond this simple strategy by dynamically selecting a subset of all executed methods for optimization, attempting to focus optimization effort on program hot spots. Systems in this category include: the Self-93 system described in “Reconciling responsiveness with performance in pure object-oriented languages”, ACM Transactions on Programming Languages and Systems, 18(4):355–400, July 1996 to Hölzle, et al.; the HotSpot JVM such as described in “The Java Hotspot performance engine architecture”, white paper available at http://java.sun.com/products/hotspot/whitepaper.html, April 1999; the IBM Java Just-in-Time compiler (version 3.0) described in “Overview of the IBM Java Just-in-Time compiler”, IBM Systems Journal, 39(1), 2000 to T. Suganama, et al.; and, JUDO as described in “Practicing JUDO: Java Under Dynamic Optimizations”, SIGPLAN 2000 Conference on Programming Language Design and Implementation, June 2000 to M. Cierniak, et al. Some second-wave virtual machines also include limited forms of online feedback-directed optimization (e.g., inlining in Self-93), but do not develop general mechanisms for adaptive online feedback-directed optimization.
Many modern programming language runtime environments and tools can benefit from runtime feedback from a program. For example, Java virtual machines may use runtime feedback to guide optimization of the running program. As another example, program understanding tools may gather runtime information and report summaries to the user. An adaptive optimization system attempts to optimize an executing program based on its current execution. Such systems typically identify sections of the program where significant runtime is spent and recompiles those sections with an optimizing compiler.
Thus, a number of research projects have explored more aggressive forms of dynamic compilation: These projects have been described in the following references: “Fast, effective dynamic compilation”, Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 149–159, Philadelphia, Pa., 21–24 May 1996, and SIGPLAN Notices, 31(5), May 1996 to J. Auslander, et al.; “Dynamo: A transparent dynamic optimization system”, SIGPLAN 2000 Conference on Programming Language Design and Implementation, June 2000 to V. Bala, et al.; “Efficient Compilation and Profile-Driven Dynamic Recompilation in Scheme”, PhD thesis, Indiana University, 1997 to R. G. Burger; “An infrastructure for profile-driven dynamic recompilation”, ICCL'98, the IEEE Computer Society International Conference on Computer Languages, May 1998, to R. G. Burger et al.; “A general approach for run-time specialization and its application to C”, Conference Record of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages}, pages 145–156, January 1996 by C. Consel et al.; “DyC: An expressive annotation-directed dynamic compiler for C”, Technical Report TR-97-03-03, University of Washington, Department of Computer Science and Engineering, March 1997 by B. Grant, et al.; “An evaluation of staged run-time optimizations in DyC”, Proceedings of the ACM SIGPLAN'99 Conference on Programming Language Design and Implementation, pages 293–304, 1999 by B. Grant, et al.; “Continuous Program Optimization”, PhD thesis, University of California, Irvine, 1999 by T. P. Kistler; “Dynamic specialization in the Fabius system”, ACM Computing Surveys, 30(3es):1–5, September 1998, Article 23 by M. Leone et al.; “Efficient incremental run-time specialization for free”, Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 281–292, 1999, by R. Marlet, et al.; and, “A system for fast, flexible, and high-level dynamic code generation”, Proceedings of the ACM SIGPLAN'97 Conference on Programming Language Design and Implementation (PLDI), pages 109–121, Las Vegas, Nev., 15–18 Jun. 1997, and SIGPLAN Notices 32(5), May 1997, by M. Poletto, et al. These aggressive forms of dynamic compilation use runtime information to tailor the executable to its current environment. Most of these systems are not fully automatic, and so far, few of these techniques have appeared in mainstream JVMs. However, these systems have demonstrated that online feedback-directed optimizations can yield substantial performance improvements.
Therefore, it would be highly desirable to provide an adaptive online feedback-directed optimization system for leading-edge JVM technology.
Previous adaptive systems such as described in the reference “Overview of the IBM Java just-in-time compiler,” IBM Systems Journal, 39(1), 2000 by T. Suganama, et al., and the reference “Reconciling responsiveness with performance in pure object-oriented languages”, ACM Transactions on Programming Languages and Systems, 18(4):355–400, July 1996 to Hölzle, et al. have relied on intrusive instrumentation in the form of method invocation counters to identify and optimize program hot spots. Two drawbacks to this approach are: 1) the overhead of incrementing a counter on every method invocation, and 2) the final optimization of a method removes the method invocation counters, preventing the method from being identified as a candidate for future recompilation.
For example, U.S. Pat. No. 5,995,754 to Hölzle, et al., describes a system (hereinafter the “Self-93” system) for compiling byte-codes associated with executing programs at run-time, and specifically directed to a mechanism for re-compiling previously compiled or interpreted code dynamically, into a more efficient form. In the “Self-93” system, use is made of an invocation tracker for tracking the number of invocations of a particular selected method. When the number of invocations exceeds a certain threshold value, a method is chosen to be compiled. Particularly, in the Self-93 system, a call stack, i.e., a thread-specific runtime data structure that keeps track of the methods that are currently active in a particular thread, is examined when an invocation counter threshold is reached with the goal of determining which active method on the call stack is a likely candidate to be compiled. The method to be compiled may then be chosen using parameterizable heuristics, such as the size of a method, with the goal that the method that had the counter exceed its threshold is ultimately inlined, and thus, compiled, into the chosen method. When this occurs such method is no longer a candidate for optimization in this context. If there are calls to this method from other methods it may be optimized in that context, but again, this can only happen once.
It would be highly desirable to provide an adaptive optimization system for a JVM that implements a sampling technique having lower overhead than invocation counters and that drives adaptive and online feedback-directed optimizations.
It would be further highly desirable to provide an adaptive optimization system for a JVM that uses multiple optimization levels to improve performance compared to using only a single level of optimization.